Two broad classes of methods can be used for the construction of low-density parity-check (LDPC) codes. One set is based on highly random graph constructions, while the other is based on structured algebraic constructions. Random graph constructions can produce LDPC codes that approach the Shannon capacity.
LDPC graph constructions normally use a “Tanner graph,” which is a bi-partite graph including “variable” nodes representing the codeword bits, and “check” nodes representing the parity checks, where a variable node is connected to a check node by an edge if and only if the corresponding entry in the parity check matrix for the code is nonzero. Tanner graphs are well known.
Although codes based on highly random Tanner graph construction can closely approach the Shannon limit, these constructions are not easy to implement in hardware because the irregular connections between check and variable nodes in the Tanner graph of the code imply high wiring complexity. In actual implementations, more structured constructions are preferred because those provide much more practical wiring, and more straightforward parallelism in the decoders.
Quasi-cyclic LDPC (QC LDPC) codes are structured graphs that use a parity check matrix. The parity check matrix is partitioned into sub-matrices that have a circulant structure. Because the structured graph is practical to implement in hardware, QC LDPC codes are used in a variety communication networks, such as those implemented according to the IEEE 802.16e, DVB-S2, and IEEE 802.11 standards.
For most applications, it is important to optimize decoding performance in a “water-fall” regime where the signal-to-noise ratio (SNR) is relatively low.
However, for some applications, optimizing water-fall performance is not sufficient. One must also avoid “error floors” that are inherent in many LDPC codes in the higher SNR regimes. An “error floor” in the performance curve means that the decoding failure rate does not continue to decrease rapidly as the SNR increases. Eliminating or lowering the error floors is particularly important for applications that require extreme reliability demands, including high density magnetic recording and high speed fiber-optic communication systems.
Generally, QC LDPC codes are constructed based on a wide variety of techniques, including finite geometries, finite fields, and combinatorial designs. Recently, there has also been great interest in a class of “convolutional,” or “spatially-coupled” codes, which are much more structured than the conventional random constructions, but have also been shown to closely approach the Shannon capacity, or even to achieve the Shannon capacity on a binary erasure channel (BEC). Those codes are significant here, because those codes can be implemented using quasi-cyclic constructions, and should thus be able to achieve very good performance while retaining the practicality of other structured QC LDPC codes.
Error floor issues for LDPC codes that are decoded using belief propagation (BP) decoders are generally caused by “trapping sets.” A trapping set is a set of a small number of bits that reinforce each other in their incorrect beliefs. Trapping sets of bits are invariably arranged in clustered short cycles in the Tanner graph for the code. One way to remove the trapping sets is to design the Tanner graph so that clusters of short cycles do not exist. An alternative, and at least conceptually simpler approach is to design codes with larger girths. The “girth” of a code is defined as a length of the shortest cycle in the Tanner graph. Removing short cycles may eliminate potentially dangerous configurations of cycles, and hopefully lower the error floor.
Codes with good water-fall performance inevitably have some irregularity in the degree-distributions of the factor or variable nodes of the code graph. For the case of QC LDPC codes, these irregular distributions are most easily described in terms of “protographs,” which are variants of Tanner graphs where bits and checks of the same type are represented by a single “proto-bit” or “proto-check.” Protographs are a well-known way to describe families of codes.
In the case of QC LDPC codes, proto-bits can, for example, represent bits belonging to the same circulant sub-matrices. The protographs that arise in codes that have been optimized for waterfall performance typically have some pairs of proto-bits and proto-checks that are connected by multiple edges. A straightforward way to construct QC LDPC codes that correspond to such protographs use QC LDPC codes where the circulant sub-matrices have rows and columns of weight greater than one. Unfortunately, those QC LDPC codes inevitably have short cycles in their Tanner graphs.
Accordingly, there is a need to provide a method for determining a QC LDPC code corresponding to a protograph, such that the QC LDPC code has a predetermined relatively high girth, even when the protograph has pairs of proto-bits and proto-checks that are connected by multiple edges.